﻿//1574. 删除最短的子数组使剩余数组有序
//给你一个整数数组 arr ，请你删除一个子数组（可以为空），使得 arr 中剩下的元素是 非递减 的。
//一个子数组指的是原数组中连续的一个子序列。
//请你返回满足题目要求的最短子数组的长度。*/



class Solution {
public:
    int findLengthOfShortestSubarray(vector<int>& arr)
    {
        //arr[0]~arr[left] 非递减
        //arr[right]~arr[n-1] 非递减
        //arr[left]<=arr[right]
        //删除arr[left+1] ~ arr[right-1]
        int n = arr.size();
        int right = arr.size() - 1;
        //枚举直到 arr[right-1] > arr[right]
        for (; right > 0 && arr[right - 1] <= arr[right]; right--);
        if (right == 0)  return  0;
        int left = 0;
        int ans = right;
        for (; left < n; left++)
        {
            while (right < n && arr[right] < arr[left])
            {
                right++;
            }
            ans = min(ans, right - left - 1);
            if (left + 1 < n && arr[left] > arr[left + 1])
            {
                break;
            }
        }
        return ans;
    }
};